package com.search;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindAllAnagrams {
	
	public static void main(String[] args) {

	}
	 public List<Integer> findAnagrams(String s, String p) {
		 List<Integer> list = new ArrayList();
		 Map<Character,Integer> need = new HashMap();
		 Map<Character,Integer> Windows = new HashMap();
		 for(char ch : p.toCharArray())
			 need.put(ch, need.getOrDefault(ch, 0) + 1);
		 int left = 0,right = 0;
		 int vaild = 0;
		 while(right < s.length()) {
			 char ch1 = s.charAt(right);
			 right++;
			  if(need.containsKey(ch1)) {
				  Windows.put(ch1, Windows.getOrDefault(ch1, 0) + 1);
				  if(Windows.get(ch1).equals(need.get(ch1))) {
					  vaild++;
				  }
			  }
			  while(vaild == need.size()) {
				  if(right - left == p.length()) {
					  list.add(left);
				  }
				  char ch2 = s.charAt(left);
				  left++;
				  if(need.containsKey(ch2)) {
					  if(Windows.get(ch2).equals(need.get(ch2))) {
						  vaild--;
					  }
					  Windows.put(ch2, Windows.getOrDefault(ch2, 0) - 1);
				  }
			  }
		 }
		 
		 return list;
	  }
}
